package com.gxc.array;

/**
 * 在一个无序数组中，求最小的第k个数。
 *
 * 解法
 * 一：
 * 排序
 *
 * 二：
 * 如果数据量不大，可以使用桶排序思想，空间换时间
 *
 * 三：
 * bfprt算法
 */
public class KMin {

    public static void main(String[] args) {
        int[] arr = new int[10];
    }

    /**
     * 改写快排
     *      随机选中一个V，数组中的其他根据V 划分为 <v ==v >v 三部分, 看 ==v 的边界是否包含 k，如果包含则返回，
     *      不包含，则单侧递归
     *      难点在于如何找到合适的V，根据V的大小，时间复杂度不一致
     * @param arr
     * @param k
     * @return
     */
    public static int process2(int[] arr, int k) {
        int[] copyArray = copyArray(arr);
        return quickSort(copyArray, 0, arr.length-1, k-1);
    }

    /**
     *
     * @param copyArray
     * @param s
     * @param e
     * @param index 目标位置
     * @return
     */
    private static int quickSort(int[] copyArray, int s, int e, int index) {
        if (s == e) return copyArray[s];
        int random = (int) (Math.random() *(e-s+1) + s);
        int v = copyArray[random];
        int[] range = partition(copyArray, s, e, v);

        if (index>=range[0] && index<= range[1]) return v;
        else if (index < range[0]) {
            return quickSort(copyArray, s, range[0]-1, index);
        } else {
            return quickSort(copyArray, range[1]+1, e, index);
        }
    }

    /**
     * 根据 随机值V ，数组分成 <v ==v >v 三部分
     * @param copyArray
     * @param s
     * @param e
     * @param v
     * @return
     */
    private static int[] partition(int[] copyArray, int s, int e, int v) {
        int[] range = new int[2];
        //记录最小边界
        int less = s-1;
        //记录最大边界
        int more = e+1;

        int cur = s;
        while (cur<more) {
            if (copyArray[cur] > v) {
                swapArray(copyArray, cur, --more);
            } else if (copyArray[cur] < v) {
                swapArray(copyArray, ++less, cur++);
            } else {
                cur++;
            }
        }
        range[0] = less+1;
        range[1] = more-1;
        return range;
    }

    /**
     *
     *
     * bfprt 算法（改写快排的优化版）
     * 数组按 5个一组组成新数组，新数组求数组的上中位数 m1，
     * 把所有新数组的上中位数 m1，构成新的数组 ，然后再次求上中位数 m2,
     * 此时的 m2 作为 随机值 v，
     * 因为m1 是 5个一组组成新数组 ，m2又是新上中位数的上中位数
     * 所以确定至少大于 m2的数总共有  n/5/2*3 = 3n/10，
     * 另一部分就只剩余  7n/10 ，
     * 通过m2 每次都能淘汰至少 3n/10的数据
     * @param arr
     * @return
     */
    public static int process(int[] arr, int k) {
        int[] copyArray = copyArray(arr);
        return bfprt(copyArray, 0, arr.length-1, k-1);
    }

    private static int bfprt(int[] copyArray, int s, int e, int index) {
        if (s == e) return copyArray[s];
        int v = bfprtRandom(copyArray, s, e);
        int[] range = partition(copyArray, s, e, v);

        if (index>=range[0] && index<= range[1]) return v;
        else if (index < range[0]) {
            return quickSort(copyArray, s, range[0]-1, index);
        } else {
            return quickSort(copyArray, range[1]+1, e, index);
        }
    }

    private static int bfprtRandom(int[] copyArray, int s, int e) {
        int size = e-s+1;
        int multiple = size/5;
        int offset = size%5==0?0:1;
        int[] media = new int[multiple+offset];

        for (int i = 0; i < media.length; i++) {
            int L = s+5*i;
            int R = s+5*(i+1)-1;
            media[i] = getMedia(copyArray, L, Math.min(e, R));
        }
        return bfprt(media, 0, media.length-1, (media.length-1)/2);
    }

    private static int getMedia(int[] copyArray, int L, int R) {
        for (int i = L; i <= R; i++) {
            for (int j = i+1; j <=R; j++) {
                if (copyArray[j]<copyArray[i]) {
                    swapArray(copyArray, i, j);
                }
            }
        }
        return copyArray[L+R/2];
    }

    private static int[] copyArray(int[] arr) {
        int[] copy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copy[i] = arr[i];
        }
        return copy;
    }

    private static void swapArray(int[] copyArray, int s, int e) {
        int temp = copyArray[s];
        copyArray[s] = copyArray[e];
        copyArray[e] = temp;
    }
}
